/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Hua YY
 * Date: 2025-01-19
 * Time: 10:50
 */
import java.util.ArrayList;
import java.util.List;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */

// 使用Pair 类型标识节点+下标
// 使用层序遍历的方式，但是使用集合的形式模拟队列
class Solution3 {
    public int widthOfBinaryTree(TreeNode root) {
        // 先把根节点入队
        List<Pair<TreeNode, Integer>> q = new ArrayList<>();
        q.add(new Pair<>(root, 1));

        int ret = 0; // 存储最终结果

        while (!q.isEmpty()) {
            // 先更新一下结果
            // 获取这一层的队头和队尾
            Pair<TreeNode, Integer> t1 = q.get(0);
            Pair<TreeNode, Integer> t2 = q.get(q.size() - 1);
            ret = Math.max(ret, t2.getValue() - t1.getValue()+1);

            // 然后遍历下一层把它们的孩子放进新的队列，进行覆盖
            List<Pair<TreeNode, Integer>> tem = new ArrayList<>();
            for(Pair<TreeNode,Integer> t : q){
                //获取当前层的当前节点
                TreeNode node = t.getKey();
                Integer index = t.getValue();
                if(node.left != null){
                    tem.add(new Pair<>(node.left,2*index));
                }
                if(node.right != null){
                    tem.add(new Pair<>(node.right,2*index+1));
                }
            }
            q = tem;
        }
        return ret;

    }
}
public class Test3 {
}
